/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date May 30, 2014
 */
package zhoujian.oj.leetcode;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given n points on a 2D plane, find the maximum number of points
 *              that lie on the same straight line.
 */
public class MaxPointsOnALine {
	
	class Point {
		int x;
		int y;
		
		Point() {
			x = 0;
			y = 0;
		}
		
		Point(int a, int b) {
			x = a;
			y = b;
		}
	}

	// details is important
	public int maxPoints(Point[] points) {
		if (points.length < 1)
			return 0;
		int res = 0;
		Map<Double, Integer> map = new HashMap<Double, Integer>();
		for (int i = 0; i < points.length; i++) {
			map.clear();
			int max = 1;
			int duplicate = 0;
			int vertical = 1;
			for (int j = 0; j < points.length; j++) {
				if (j == i)
					continue;
				if (points[j].x == points[i].x && points[j].y == points[i].y) {
					duplicate++;
					continue;
				}
				if (points[j].x == points[i].x) {
					vertical++;
					continue;
				}
				double k = (double) (points[j].y - points[i].y) / (points[j].x - points[i].x);
				if (!map.containsKey(k))
					map.put(k, 2);
				else 
					map.put(k, map.get(k) + 1);
			}
			
			for (Iterator<Double> it = map.keySet().iterator(); it.hasNext();) {
				int cur = map.get(it.next());
				max = max > cur ? max : cur;
			}
			
			max = max > vertical ? max : vertical;
			max += duplicate;
			res = res > max ? res : max;
		}
		return res;
	}

	@Test
	public void test() {
		Point[] points = new Point[] {
//			new Point(-4, 1),
//			new Point(-7, 7),
//			new Point(-1, 5),
//			new Point(9, -25),
			new Point(0, 0),
			new Point(0, 1)
		};
		
		System.out.println(maxPoints(points));
	}
}
